package graph;

import java.util.ArrayList;
import java.util.Arrays;

public class DijkstraAdj {

	private int[] prev;

	private static final int INF = Integer.MAX_VALUE;

	public int[] dijkstra(ArrayList<ArrayList<Integer[]>> adj, int vertexNum,
			int source) {
		prev = new int[vertexNum];
		boolean[] visit = new boolean[vertexNum];
		int[] dist = new int[vertexNum];
		Arrays.fill(dist, INF);
		dist[source] = 0;
		prev[source] = -1;
		int min, u;
		for (int i = 1; i < vertexNum; i++) {
			min = INF;
			u = -1;
			for (int j = 0; j < vertexNum; j++)
				if (!visit[j] && dist[j] < min) {
					min = dist[j];
					u = j;
				}
			if (u == -1) {
				break;
			}
			visit[u] = true;
			for (Integer[] e : adj.get(u)) {
				if (!visit[e[0]] && dist[e[0]] > dist[u] + e[1]) {
					dist[e[0]] = dist[u] + e[1];
					prev[e[0]] = u;
				}
			}
		}
		return dist;
	}

	public int[] getPath() {
		return prev;
	}

}
